#include<vector>
using namespace std;

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int v[2] = {0,0};
        int n[2] = {0,0};
        for (int i = 0; i < nums.size(); ++i) {
            bool flag = false;
            for (int k = 0; k < 2; ++k) {
                if (n[k] != 0&&v[k] == nums[i]) {
                    flag = true;
                    ++n[k];
                    break;
                }
            }
            if (!flag) {
                for (int k = 0; k < 2; ++k) {
                    if (n[k] == 0) {
                        v[k] = nums[i];
                        n[k] = 1;
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    --n[0];
                    --n[1];
                }
            }
        }
        vector<int> res;
        for (int k = 0; k < 2; ++k) {
            if (n[k] == 0) continue;
            n[k] = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (v[k] == nums[i])
                    ++n[k];
            }
            if(n[k]>nums.size()/3)
                res.push_back(v[k]);
        }
        return res;
    }
};